package com.czk.stack.polandPractice;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author:ChenZhangKun
 * @Date: 2021/5/30 11:17
 */
public class PolandNotationDemo {
    public static void main(String[] args) {
        System.out.println(getResult(infixToSuffixExpression(toInfixExpresion("(3+4)*5-6*6"))));
    }

    public static int getResult(List<String> list) {
        // 创建栈
        Stack<String> stack = new Stack<>();
        // 遍历
        list.forEach(x -> {
            if (x.matches("\\d+")) {
                // 是数字
                // 入栈
                stack.push(x);
            } else {
                // 符号
                // 弹栈
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                // 计算结果
                int result = 0;
                switch (x) {
                    case "+":
                        result = num1 + num2;
                        break;
                    case "-":
                        result = num2 - num1;
                        break;
                    case "/":
                        result = num2 / num1;
                        break;
                    case "*":
                        result = num2 * num1;
                }
                // 压入栈
                stack.push(result + "");
            }
        });
        return Integer.parseInt(stack.pop());
    }

    /**
     * 中缀表达式转后缀表达式
     * 取出括号
     *
     * @param list
     * @return
     */
    public static List<String> infixToSuffixExpression(List<String> list) {
        // 定义符号栈
        Stack<String> stack = new Stack();
        // 定义数字栈
        List<String> numStack = new ArrayList<>(10);
        // 遍历
        for (String s : list) {
            // 判断类型
            if (s.matches("\\d+")) {
                // 数字
                numStack.add(s);
            } else if (s.equals("(")) {
                // 直接进入符号栈
                stack.push(s);
            } else if (s.equals(")")) {
                // 将符号栈里非左括号的字符全部弹出
                while (!stack.peek().equals("(")) {
                    // 加入数字栈
                    numStack.add(stack.pop());
                }
                // 小括号弹出栈顶
                stack.pop();
            } else {
                if (stack.isEmpty()||stack.peek().equals("(")){
                    stack.push(s);
                }else {
                    // 此时是运算符
                    while (stack.size() != 0 && Operation.getPriority(stack.peek()) >= Operation.getPriority(s)) {
                        // 弹出加入数字栈
                        numStack.add(stack.pop());
                    }
                    // 压入符号栈
                    stack.push(s);
                }
            }
        }
        // 将剩余的符号栈中的数压入数字栈
        while (stack.size() != 0) {
            numStack.add(stack.pop());
        }
        return numStack;
    }

    public static List<String> toInfixExpresion(String inFixExpresion) {
        List<String> list = new ArrayList<>(10);
        // 遍历
        int index = 0;
        char ch = ' ';
        do {
            ch = inFixExpresion.charAt(index);
            if (ch > 57 || ch < 48) {
                // 不是数字，直接进入集合
                list.add(ch + "");
                index++;
            } else {
                String s = "";
                // 是数字
                while (index < inFixExpresion.length() && (ch = inFixExpresion.charAt(index)) >=48 && (ch = inFixExpresion.charAt(index))<= 57) {
                    // 累加
                    s += ch;
                    index++;
                }
                list.add(s);
            }
        } while (index < inFixExpresion.length());
        // 返回
        return list;
    }
}

class Operation {
    public static final int ADD = 1;
    public static final int SUB = 1;
    public static final int MUL = 2;
    public static final int DIV = 2;

    /**
     * 拿到优先级
     *
     * @param operation
     * @return
     */
    public static int getPriority(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
        }
        return result;
    }
}
